def exist(board: list[list[str]], word: str) -> bool:
    def backtrack(i, j, k):
        # 如果已经匹配到单词的末尾，返回True
        if k == len(word):
            return True
        # 先判断边界条件，确保当前字符是有效的且与目标字符匹配
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
            return False
        
        # 暂时保存当前字符，并将该格子标记为已访问
        temp, board[i][j] = board[i][j], '/'
        
        # 在四个方向上进行回溯，向上下左右四个方向继续搜索
        for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if backtrack(x, y, k + 1):  # 继续匹配下一个字符
                return True
        
        # 回溯到当前格子时恢复原状态
        board[i][j] = temp  
        return False

    # 遍历整个board，尝试从每个格子开始进行回溯搜索
    for i in range(len(board)):
        for j in range(len(board[0])):
            if backtrack(i, j, 0):  # 从当前格子开始回溯
                return True
    return False

# 示例
board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]
word = "ABFS"
print(exist(board, word))  # 输出 True
